﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;

public class Solution300
{
    //找到其中最长严格递增子序列的长度。
    //这个最长的递增，那么前面一个肯定也是递增
    //这个数组分成一些固定增长的数组
    //找到最长的就可以了
    public int LengthOfLIS(int[] nums)
    {
        int len = nums.Length;
        if(len == 0) return 0;  
        //前面最长，但是加上这个不一定是最长了
        int[] dp = new int[nums.Length];
        dp[0] = 1;//只有一个元素的数组的最大子序列长度为1
        int max = 1;

        for (int i = 1; i <nums.Length; i++)//找长度为i的数组的最大子序列
        {
            dp[i] = 1;//dp[i]=0初始值，导致nums[i] > nums[j]没有满足条件应该也是从1 开始加
            for (int j = 0; j < i; j++)
            {
                

                if (nums[i] > nums[j]) //才有可能形成最长序列
                {

                    dp[i] = Math.Max(dp[i], dp[j] + 1);

                }

             


            }


            max = Math.Max(dp[i], max);


        }

        //return dp[nums.Length];//不是以最后一个数字为结尾的
        return max;//不是以最后一个数字为结尾的

    }
}
    class Program300
    {

        static void Main300(string[] args)
        {
            Solution300 solution = new Solution300();
            int[] nums = [10, 9, 2, 5, 3, 7, 101, 18];
            int res = solution.LengthOfLIS(nums);
            Console.WriteLine("最长递增子序列长度为:" + res);
        }
    }

